home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / NTUMIN10.ARJ / CAMPC.C < prev    next >
C/C++ Source or Header  |  1992-03-09  |  11KB  |  342 lines
  1. /****************************************************************************
  2.  *
  3.  *      Program name : CAMPC.C
  4.  *
  5.  *      This is the actual minimization algorithm. Variation from the actual
  6.  *    CAMP algorithm is as follows:
  7.  *        1.    Minterms with adjacency 0 or 1 is minimised first
  8.  *        2.    Select next minterm with lowest adjacency wrt b-array
  9.  *        3.    To shrink the CPT, select an adjacent term, mi that has the
  10.  *            largest wi AND is already covered
  11.  *
  12.  * --------------------------------------------------------------------------
  13.  *    Copyright (c) 1992. All Rights Reserved. Nanyang Technological
  14.  *    University.
  15.  *
  16.  *    You are free to use, copy and distribute this software and its
  17.  *    documentation providing that:
  18.  *
  19.  *        NO FEE IS CHARGED FOR USE, COPYING OR DISTRIBUTION.
  20.  *
  21.  *        IT IS NOT MODIFIED IN ANY WAY.
  22.  *
  23.  *        THE COPYRIGHT NOTICE APPEAR IN ALL COPIES.
  24.  *
  25.  *    This program is provided "AS IS" without any warranty, expressed or
  26.  *    implied, including but not limited to fitness for any particular
  27.  *    purpose.
  28.  *
  29.  *    If you find NTUMIN fast, easy, and useful, a note or comment would be
  30.  *    appreciated. Please send to:
  31.  *
  32.  *        Boon-Tiong Tan or Othman Bin Ahmad
  33.  *        School of EEE
  34.  *        Nanyang Technological University
  35.  *        Nanyang Avenue
  36.  *        Singapore 2263
  37.  *        Republic of Singapore
  38.  *
  39.  ***************************************************************************/
  40.  
  41. #include <stdio.h>
  42. #include <stdlib.h>
  43. #include <string.h>
  44. #define mask8 255
  45.  
  46. unsigned char   *campc(a, b)              /* pointer to a & b array passed */
  47. unsigned char   *a, *b;
  48.  
  49. {
  50.    unsigned short   pterm, ma, mb, *pm, pos;
  51.    unsigned  long   m, topow();
  52.    register  long   i, wo, wi;
  53.    register  char   j;
  54.          char   test;
  55.    unsigned  char   *c, *d, *e, *s, *temp, count, adj0, adji;
  56.    unsigned  char   n, adj, adjacency(), nspm, cover;
  57.    unsigned  char   *adjacent(), *reduce(), *cpt(), *ssm(), adj_of_mi();
  58.  
  59.  
  60.    mb = *(b+2)<<8 | *(b+1);            /* no. of minterms in b-array */
  61.  
  62.    n    = *a;                          /* no. of variables */
  63.    nspm = *(a+3);                      /* no. of bytes/minterm */
  64.    ma = *(a+2)<<8 | *(a+1);            /* no. of minterms in a-array */
  65.  
  66.    temp = (unsigned char *) malloc(nspm+1);        /* temporary storage */
  67.    if (temp == 0)
  68.       {
  69.      printf("Out of memory -- CAMPC, *temp\n");
  70.      printf("Program terminated - 1\n");
  71.      exit(0);
  72.       }
  73.  
  74.    s = (unsigned char *) malloc(4);                /* header of s-array */
  75.    if (s == 0)
  76.       {
  77.      printf("Out of memory -- CAMPC, *s\n");
  78.      printf("Program terminated - 2\n");
  79.      exit(0);
  80.       }
  81.  
  82.    pterm = 0;                                /* no. of product term */
  83.  
  84.    /***
  85.     ***  MINIMIZE ALL MINTERMS WITH ADJACENCY OF 0 & 1 FIRST
  86.     ***/
  87.  
  88.    for (i=0; i<mb; i++)                      /* for adj = 0 or 1 */
  89.       {
  90.      *b = n;                             /* assign back to n */
  91.  
  92.      memcpy(temp, (b+4+nspm*i), nspm);   /* pick a minterm from b-array */
  93.      c = adjacent(temp, a, 1);           /* obtain the adjacent terms */
  94.      adj = *(c+1);                       /* adjacency of minterm */
  95.  
  96.      if (adj <= 1)                       /* adjacency 0 or 1 */
  97.         {
  98.            d = cpt(c);                   /* generate CPT */
  99.  
  100.            s = (unsigned char *) realloc(s,4+n*(pterm+1));   /* more space */
  101.            if (s == 0)
  102.           {
  103.              printf("Out of memory -- CAMPC, *s\n");
  104.              printf("Program terminated - 3\n");
  105.              exit(0);
  106.           }
  107.            memcpy ((s+4+n*pterm),d,n);   /* add CPT to soln array */
  108.            pterm++;                      /* product term count */
  109.  
  110.            b = reduce(c,b,i);            /* remove minterms covered from b-array */
  111.            i = (char) *b;                /* index pointer of b-array */
  112.            mb = *(b+2)<<8 | *(b+1);      /* value of mb altered in b-array */
  113.  
  114.            free(d);                    /* free pointer */
  115.         }
  116.      free(c);                            /* free pointer */
  117.       }
  118.  
  119.     /***
  120.      ***  MINIMIZE MINTERMS WITH ADJACENCY GREATER THAN 1
  121.      ***/
  122.  
  123.     while (mb > 0)
  124.        {
  125.       adj0 = 255;                     /* max for 8-bit */
  126.  
  127.       *b = n;                         /* assign back to n */
  128.  
  129.       /***
  130.        ***  SELECT 1ST MINTERM WITH LOWEST ADJACENCY WRT B-ARRAY
  131.        ***/
  132.  
  133.       for (i=0; i<mb; i++)
  134.          {
  135.         memcpy(temp, (b+4+nspm*i), nspm);    /* pick a minterm */
  136.         adji = adjacency(temp, b);           /* obtain adjacency */
  137.  
  138.         if (adji<adj0)                       /* look for lowest adj */
  139.            {
  140.               adj0 = adji;
  141.               pos = i;                       /* position of minterm */
  142.            }
  143.           }
  144.        memcpy(temp, (b+4+nspm*pos), nspm);       /* pick the required minterm */
  145.  
  146.        /***
  147.         ***  GENERATE SSM AND TEST FOR COVERAGE BY FUNCTION
  148.         ***/
  149.  
  150.        c = adjacent(temp, a, 255);          /* obtain adjacent terms */
  151.        adj = *(c+1);                        /* adjacency of minterms */
  152.        d = cpt(c);                          /* generate CPT */
  153.        e = ssm(d);                          /* generate SSM */
  154.        m = topow(*(e+1));                   /* no. of SSM terms */
  155.  
  156.        for (j=0; j<m; j++)                  /* check for SSM coverage */
  157.           {
  158.          memcpy (temp, (e+4+nspm*j), nspm);   /* pick SSM term */
  159.          test = exist (temp, a, ma);
  160.          if (test == -1)                /* SSM term not in a-array */
  161.              break;
  162.           }
  163.  
  164.        /***
  165.         ***  ALL SSM COVERED BY THE FUNCTION, SELECT CPT AS PRODUCT TERM
  166.         ***/
  167.  
  168.        if (test == 0)                       /* all SSM's covered by fn */
  169.           {
  170.          if (m > 65536)                  /* too many SSM terms */
  171.             {
  172.                printf("Product Term Too Huge \n");
  173.                printf("Program terminated \n");
  174.                exit(0);
  175.             }
  176.          *(e+1) = (m-1) & mask8;         /* no. of SSM terms minus 1 */
  177.          *(e+2) = (m-1)>>8 & mask8;
  178.          b = reduce(e,b,i);             /* remove minterms covered from b-array */
  179.          mb = *(b+2)<<8 | *(b+1);       /* no. of minterms in b-array */
  180.  
  181.          s = (unsigned char *) realloc(s, 4+n*(pterm+1)); /* more space */
  182.          if (s == 0)
  183.             {
  184.                printf("Out of memory -- CAMPC, *s\n");
  185.                printf("Program terminated - 4\n");
  186.                exit(0);
  187.             }
  188.          memcpy((s+4+n*pterm),d,n);     /* add CPT to soln array */
  189.          pterm++;                       /* no. of product terms */
  190.  
  191.          free(d);                       /* free pointers */
  192.          free(e);
  193.           }
  194.        else
  195.           {
  196.          /***
  197.           ***  SSM NOT COVERED BY THE FUNCTION
  198.           ***/
  199.  
  200.          free(d);                       /* free pointer */
  201.          cover =0;                      /* coverage status */
  202.  
  203.          while (!cover)        /* do until shrinked SSM is covered */
  204.             {
  205.                /***
  206.             ***  OBTAIN AN ARRAY, PM OF POSITIONS OF ADJACENT TERMS, MI WITH THE LARGEST WI
  207.             ***/
  208.  
  209.                wo = -1;                        /* initial value */
  210.                for (j=0; j<adj; j++)           /* do for all adjacent terms */
  211.               {
  212.                  memcpy(temp,(c+4+nspm*(j+1)),nspm); /* pick adjacent term */
  213.  
  214.                  wi = adj_of_mi(temp,e,a);           /* obtain wi */
  215.                  if (wi>wo)
  216.                 {
  217.                    if (wo != -1)                 /* not the first */
  218.                       free(pm);
  219.                    wo = wi;                      /* new lowest value */
  220.                    count = 1;                    /* reset count to 1 */
  221.  
  222.                    pm = (unsigned short *) malloc(2);  /* space for pm */
  223.                    if (pm==0)
  224.                       {
  225.                      printf("Out of memory -- CAMPC, *pm\n");
  226.                      printf("Program terminated - 5\n");
  227.                      exit(0);
  228.                       }
  229.                    *pm = j;                      /* first element */
  230.                 }
  231.                  else if (wi==wo)                    /* wi as large */
  232.                 {
  233.                    count++;                      /* no. of element in pm-array */
  234.  
  235.                    pm = (unsigned short *) realloc (pm, 2*count);  /* more space */
  236.                    if (pm==0)
  237.                       {
  238.                      printf("Out of memory -- CAMPC, *pm\n");
  239.                      printf("Program terminated - 6\n");
  240.                      exit(0);
  241.                       }
  242.                    *(pm+count-1) = j;            /* elements of pm-array */
  243.                 }
  244.               }
  245.                free(e);
  246.  
  247.                /***
  248.             ***  SELECT FROM PM-ARRAY, AN ADJACENT TERM THAT HAS ALREADY BEEN COVERED
  249.             ***/
  250.  
  251.                for (j=0; j<count; j++)              /* do for all element in pm-array */
  252.               {
  253.                  memcpy(temp, (c+4+nspm*(1+ *(pm+j))), nspm);    /* pick adj term */
  254.                  test = exist(temp,b,mb);
  255.                  if (test == -1)                               /* already covered */
  256.                 break;
  257.               }
  258.  
  259.                if (j==count)                     /* select the 1st if all not covered */
  260.               j = 0;
  261.  
  262.                adj--;                            /* no. of adj terms in c-array */
  263.                *(c+1) = adj;                     /* adjacency after shrinking CPT */
  264.                pos = *(pm+j);                    /* required position of adj term */
  265.  
  266.                free(pm);                         /* free pointer */
  267.  
  268.                /***
  269.             ***  SHRINK CPT (REMOVE 1 ADJACENT TERM FROM C-ARRAY), GENERATE NEW CPT, SSM
  270.             ***  AND TEST FOR COVERAGE BY FUNCTION
  271.             ***/
  272.  
  273.                memcpy((c+4+nspm*(1+pos)), (c+4+nspm*(2+pos)), nspm*(adj-pos));  /* shrink CPT */
  274.  
  275.                c = (unsigned char*) realloc(c, 4+nspm*(1+adj));   /* reduce space */
  276.                if (c==0)
  277.               {
  278.                  printf("Out of memory -- CAMPC, *c\n");
  279.                  printf("Program terminated - 7\n");
  280.                  exit(0);
  281.               }
  282.  
  283.                d = cpt(c);                  /* generate CPT */
  284.                e = ssm(d);                  /* generate SSM */
  285.                m = topow(*(e+1));           /* no. of SSM terms */
  286.  
  287.                for (i=0; i<m; i++)          /* check SSM coverage by function */
  288.               {
  289.                  memcpy(temp, (e+4+nspm*i), nspm);  /* pick SSM term */
  290.                  test = exist(temp,a,ma);
  291.                  if (test == -1)                    /* SSM term not covered */
  292.                 break;
  293.               }
  294.  
  295.                /***
  296.             ***  SHRINKED SSM COVERED BY FUNCTION, REDUCE B-ARRAY
  297.             ***  AND SELECT SHRINKED CPT AS PRODUCT TERM
  298.             ***/
  299.  
  300.                if (test==0)                   /* SSM covered */
  301.               {
  302.                  if (m > 65536)                  /* too many SSM terms */
  303.                 {
  304.                    printf("Product Term Too Huge \n");
  305.                    printf("Program terminated \n");
  306.                    exit(0);
  307.                 }
  308.                  *(e+1) = (m-1) & mask8;         /* no. of SSM terms minus 1 */
  309.                  *(e+2) = (m-1)>>8 & mask8;
  310.                  b = reduce(e, b, i);     /* remove minterms covered from b-array */
  311.                  mb = *(b+2)<<8 | *(b+1); /* no. of minterms in b-array */
  312.  
  313.                  s = (unsigned char *) realloc(s, 4+n*(pterm+1));  /* more space */
  314.                  if (s==0)
  315.                 {
  316.                    printf("Out of memory -- CAMPC, *s\n");
  317.                    printf("Program terminated - 8\n");
  318.                    exit(0);
  319.                 }
  320.                  memcpy ((s+4+n*pterm), d, n);      /* add shrinked CPT to soln array */
  321.                  pterm++;                           /* no. of product terms */
  322.  
  323.                  cover = 1;                         /* coverage status */
  324.                  free(e);                           /* free pointer */
  325.               }
  326.                free (d);                      /* free pointer */
  327.             }
  328.           }
  329.       free(c);                   /* free pointer */
  330.       }
  331.    *s = n;                           /* no. of variables */
  332.    *(s+1) = pterm & mask8;           /* no. of product terms in 2 bytes */
  333.    *(s+2) = pterm>>8 & mask8;
  334.  
  335.    free(temp);                       /* free pointer */
  336.    free(a);
  337.    free(b);
  338.  
  339.    return(s);                        /* return solution array */
  340. }
  341.  
  342.